package com.example.algorithms.recursion;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author Zhang Jie
 * @Date 10/19/20
 * @Version 1.0
 *
 * 青蛙跳台阶问题：一次只能跳1或2级，问到n级台阶有多少种跳法
 * f(n)=f(n-1)+f(n-2)
 */

public class FrogJumping {
    /**
     *优化，将重复的结果缓存起来
     */
    private static Map<Integer,Integer> map=new HashMap<>();
    public static int f(int n){
        if(n==1 || n==2){
            System.out.println(n+"="+n);
            return n;
        }
        if(map.containsKey(n)){
            return map.get(n);
        }
        int result = f(n-1)+f(n-2);
        map.put(n,result);
        System.out.println(n+"="+result);
        return result;
    }

    /**
     * TODO
     * @param n
     * @return
     */
    public static int byDynamicProgramming(int n){

        return 0;
    }
}
